package week_nine;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

public class SlidingWindowMaximum_239 {

    //单调队列 双端队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];

        Deque<Integer> queue = new LinkedList<>();

        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }

        for (int i = k - 1; i <= n - 1; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);

            while (queue.peek() < i + 1 - k) {
                queue.poll();
            }

            res[i + 1 - k] = nums[queue.peek()];

        }
        return res;
    }

    //TreeSet TreeMap
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];

        TreeMap<Integer, Integer> map = new TreeMap<>();


        for (int i = 0; i < k; i++) {
            map.put(nums[i], i);
        }

        for (int i = k - 1; i <= n - 1; i++) {

            map.put(nums[i], i);

            while (map.lastEntry().getValue() < i + 1 - k) {
                map.remove(map.lastKey());
            }

            res[i + 1 - k] = map.lastKey();

        }
        return res;
    }
}
